// 15 面向对象程序设计
/**
 * 面向对象程序设计基于三个基本概念：数据抽象、继承和动态绑定。第7章已经介绍了数据抽象的知识，本章将介绍继承和动态绑定。
 * 继承和动态绑定对程序的编写有两方面的影响：一是我们可以更容易地定义与其他类相似但不完全相同的新类；二是在使用这些彼此相似的类编写程序时，我们可以在一定程度上忽略掉它们的区别。
 * 在很多程序中都存在着一些相互关联但是有细微差别的概念。
 * 例如，书店中不同书籍的定价策略可能不同：有的书籍按原价销售，有的则打折销售。有时，我们给那些购买书籍超过一定数量的顾客打折；另一些时候，则只对前多少本销售的书籍打折，之后就调回原价，等等。
 * 面向对象的程序设计（OOP）适用于这类应用。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <memory>
#include <new>
using namespace std;
#include "../Chapter13/13.5.cc" // 不能编译，因为重复定义的main函数
#include "../Chapter12/12.1.6.cc" // 不能编译，因为重复定义的main函数
#include <functional>
#include "../VisualStudio2012/15/Quote.h"
#include "../VisualStudio2012/12/TextQuery.h"

// 这是个抽象基类，具体的查询类型从中派生，所有成员都是private的
class Query_base {
    friend class Query;
protected:
    using line_no = TextQuery::line_no; // 用于eval函数
    virtual ~Query_base() = default;
private:
    // eval返回与当前Query匹配的QueryResult
    virtual QueryResult eval(const TextQuery&) const = 0;
    // rep是表示查询的一个string
    virtual string rep() const = 0;
};

// 这是一个管理Query_base继承体系的接口类
class Query  {
    // 这些运算符需要访问接受shared_ptr的构造函数，而该函数时私有的
    friend Query operator~(const Query&);
    friend Query operator|(const Query&, const Query&);
    friend Query operator&(const Query&, const Query&);
public:
    Query(const string &s); // 构建一个新的WordQuery
    // 接口函数：调用对应的Query_base操作
    QueryResult eval(const TextQuery &t) const { return q->eval(t); }
    string rep() const { return q->rep(); }
private:
    shared_ptr<Query_base> q;
    Query(shared_ptr<Query_base> query) : q(query) {}
};

std::ostream &operator<<(std::ostream &os, const Query &query)
{
    // Query::rep通过它的Query_base指针对rep()进行了虚调用
    return os << query.rep();
}

class WordQuery : public Query_base {
    friend class Query; // 为了Query使用WordQuery的构造函数
    WordQuery(const string &s) : query_word(s) {}
    // 具体的类：WordQuery将定义所有继承而来的纯虚函数
    QueryResult eval(const TextQuery &t) const override { return t.query(query_word); }
    string rep() const override { return query_word; }
    string query_word; // 要查找的单词

};
inline Query::Query(const string &s) : q(new WordQuery(s)) {}

class NotQuery : public Query_base {
    friend Query operator~(const Query &);
    NotQuery(const Query &q) : query(q) {}
    // 具体的类：NotQuery将定义所有继承而来的纯虚函数
    string rep() const override { return "~(" + query.rep() + ")"; }
    QueryResult eval(const TextQuery &t) const override; // 只声明暂未定义
    Query query;
};
inline Query operator~(const Query &operand)
{
    return shared_ptr<Query_base>(new NotQuery(operand));
}

class BinaryQuery : public Query_base {
protected:
    BinaryQuery(const Query &l, const Query &r, const string &s) : lhs(l), rhs(r), opSym(s) {}
    // 抽象类：BinaryQuery不定义eval
    string rep() const override { return "(" + lhs.rep() + opSym + rhs.rep() + ")"; }
    Query lhs,rhs;
    string opSym;
};

class AndQuery : public BinaryQuery {
    friend Query operator&(const Query&, const Query&);
    AndQuery(const Query &l, const Query &r) : BinaryQuery(l, r, "&") {}
    // 具体的类：AndQuery继承了rep并且定义了其他纯虚函数
    QueryResult eval(const TextQuery &t) const override; // 只声明暂未定义
};
inline Query operator&(const Query &lhs, const Query &rhs)
{
    return shared_ptr<Query_base>(new AndQuery(lhs, rhs));
}
class OrQuery : public BinaryQuery {
    friend Query operator|(const Query&, const Query&);
    OrQuery(const Query &l, const Query &r) : BinaryQuery(l, r, "|") {}
    // 具体的类：OrQuery继承了rep并且定义了其他纯虚函数
    QueryResult eval(const TextQuery &t) const override; // 只声明暂未定义
};
inline Query operator|(const Query &lhs, const Query &rhs)
{
    return shared_ptr<Query_base>(new OrQuery(lhs, rhs));
}

QueryResult OrQuery::eval(const TextQuery &t) const
{
    // 通过Query成员lsh和rhs进行的虚调用
    // 调用eval返回每个运算对象的QueryResult
    auto right = rhs.eval(t), left = lhs.eval(t);
    // 将左侧运算对象的行号拷贝到结果set中
    auto ret_lines = make_shared<set<line_no>>(left.begin(),left.end());
    // 插入右侧运算对象所得的行号
    ret_lines->insert(right.begin(),right.end());
    // 返回一个新的QueryResult，它表示lhs和rhs的并集
    return QueryResult(rep(), ret_lines, left.get_file()); // 因为left和right指向的是同一个文件，所以使用哪个执行get_file函数并不重要。
};

QueryResult AndQuery::eval(const TextQuery &t) const
{
    // 通过Query运算对象进行的虚调用，以获得运算对象的查询结果set
    auto right = rhs.eval(t), left = lhs.eval(t);
    // 保存left和right交集的set
    auto ret_lines = make_shared<set<line_no>>();
    // 其中我们使用标准库算法set_intersection来合并两个set，关于set_intersection在附录A.2.8（第779页）中有详细的描述。
    // set_intersection算法接受五个迭代器。它使用前四个迭代器表示两个输入序列（参见10.5.2节，第368页），最后一个实参表示目的位置。该算法将两个输入序列中共同出现的元素写入到目的位置中。
    set_intersection(left.begin(), left.end(), right.begin(), right.end(),
                     inserter(*ret_lines, ret_lines->begin()));
    return QueryResult(rep(), ret_lines, left.get_file());
}

QueryResult NotQuery::eval(const TextQuery &t) const
{
    // 通过Query运算对象对eval进行虚调用
    auto result = query.eval(t);
    // 开始时结果set为空
    auto ret_lines = make_shared<set<line_no>>();
    // 我们必须在运算对象出现的所有行中进行迭代
    auto beg = result.begin(), end = result.end();
    // 对于输入文件的每一行，如果该行不在result当中，则将其添加到ret_lines
    auto sz = result.get_file()->size();
    for (size_t n =0; n != sz; ++n) {
        // 如果我们还没处理完result的所有行
        // 检查当前行是否存在
        if(beg == end || *beg != n)
            ret_lines->insert(n); // 如果不在result当中，添加这一行
        else if(beg != end)
            ++beg; // 否则继续获取result的下一行（如果有的话）
    }
    return QueryResult(rep(), ret_lines, result.get_file());
}

int main()
{
    // 15.9 文本查询程序再探
    // 接下来，我们扩展12.3节（第430页）的文本查询程序，用它作为说明继承的最后一个例子。在上一版的程序中，我们可以查询在文件中某个指定单词的出现情况。
    // 我们将在本节扩展该程序使其支持更多更复杂的查询操作。
    /**
     * 我们的系统将支持如下查询形式。
     * · 单词查询，用于得到匹配某个给定string的所有行：Executing Query for: Daddy
     * · 逻辑非查询，使用~运算符得到不匹配查询条件的所有行：Executing Query for: ～(Alice)
     * · 逻辑或查询，使用 | 运算符返回匹配两个条件中任意一个的行：Executing Query for: (hair | Alice)
     * · 逻辑与查询，使用&运算符返回匹配全部两个条件的行：fiery &bird | wind
     * 此外，我们还希望能够混合使用这些运算符，比如：fiery &bird | wind
    */

    // 15.9.1 面向对象的解决方案
    // 我们可能会认为使用12.3.2节（第432页）的TextQuery类来表示单词查询，然后从该类中派生出其他查询是一种可行的方案。然而，这样的设计实际上存在缺陷。
    // 我们应该将几种不同的查询建模成相互独立的类，这些类共享一个公共基类：
    /**
     * WordQuery // Daddy
     * NotQuery  // ~Alice
     * OrQuery   // hair | Alice
     * AndQuery  // hair & Alice
    */

    // 关键概念：继承与组合
    // 继承体系的设计本身是一个非常复杂的问题，已经超出了本书的范围。然而，有一条设计准则非常重要也非常基础，每个程序员都应该熟悉它。
    // 当我们令一个类公有地继承另一个类时，派生类应当反映与基类的“是一种（Is A）”关系。在设计良好的类体系当中，公有派生类的对象应该可以用在任何需要基类对象的地方。
    // 类型之间的另一种常见关系是“有一个（Has A）”关系，具有这种关系的类暗含成员的意思。

    // 抽象基类
    // 因为所有这些类都共享同一个接口，所以我们需要定义一个抽象基类（参见15.4节，第541页）来表示该接口。
    // 我们的Query_base类将把eval和rep定义成纯虚函数（参见15.4节，第541页），其他代表某种特定查询类型的类必须覆盖这两个函数。
    // 我们将从Query_base直接派生出WordQuery和NotQuery。AndQuery和OrQuery都具有系统中其他类所不具备的一个特殊属性：它们各自包含两个运算对象。
    //   为了对这种属性建模，我们定义另外一个名为BinaryQuery的抽象基类，该抽象基类用于表示含有两个运算对象的查询。AndQuery和OrQuery继承自BinaryQuery，而BinaryQuery继承自Query_base。

    // 将层次关系隐藏于接口类中
    /**
     * 我们的程序将致力于计算查询结果，而非仅仅构建查询的体系。为了使程序能正常运行，我们必须首先创建查询命令，最简单的办法是编写C++表达式。
     * 例如，可以编写下面的代码来生成之前描述的复合查询：[插图] Query q = Query("fiery") & Query("bird") | Query("wind");")
     * 如上所述，其隐含的意思是用户层代码将不会直接使用这些继承的类；相反，我们将定义一个名为Query的接口类，由它负责隐藏整个继承体系。
     * Query类将保存一个Query_base指针，该指针绑定到Query_base的派生类对象上。Query类与Query_base类提供的操作是相同的：
     *   eval用于求查询的结果，rep用于生成查询的string版本，同时Query也会定义一个重载的输出运算符用于显示查询。
    */

    // 理解这些类的工作机理
    // 对于面向对象编程的新手来说，要想理解一个程序，最困难的部分往往是理解程序的设计思路。一旦你掌握了程序的设计思路，接下来的实现也就水到渠成了。

    // 15.9.2 Query_base类和Query类
    // eval和rep都是纯虚函数，因此Query_base是一个抽象基类（参见15.4节，第541页）。因为我们不希望用户或者派生类直接使用Query_base，所以它没有public成员。
    // 所有对Query_base的使用都需要通过Query对象，因为Query需要调用Query_base的虚函数，所以我们将Query声明成Query_base的友元。

    // Query类
    // Query类对外提供接口，同时隐藏了Query_base的继承体系。每个Query对象都含有一个指向Query_base对象的shared_ptr。因为Query是Query_base的唯一接口，所以Query必须定义自己的eval和rep版本。

    // Query的输出运算符

    // 15.9.3 派生类
    // 对于Query_base的派生类来说，最有趣的部分是这些派生类如何表示一个真实的查询。其中WordQuery类最直接，它的任务就是保存要查找的单词。其他类分别操作一个或两个运算对象。
    // NotQuery有一个运算对象，AndQuery和OrQuery有两个。在这些类当中，运算对象可以是Query_base的任意一个派生类的对象：一个NotQuery对象可以被用在WordQuery、AndQuery、OrQuery或另一个NotQuery中。
    // 为了支持这种灵活性，运算对象必须以Query_base指针的形式存储，这样我们就能把该指针绑定到任何我们需要的具体类上。

    // WordQuery类
    // 一个WordQuery查找一个给定的string，它是在给定的TextQuery对象上实际执行查询的唯一一个操作：
    // 定义了WordQuery类之后，我们就能定义接受string的Query构造函数了：

    // NotQuery类及~运算符
    // ~运算符生成一个NotQuery，其中保存着一个需要对其取反的Query：

    // BinaryQuery类
    // BinaryQuery类也是一个抽象基类，它保存操作两个运算对象的查询类型所需的数据：
    // BinaryQuery不定义eval，而是继承了该纯虚函数。因此，BinaryQuery也是一个抽象基类，我们不能创建BinaryQuery类型的对象。

    // AndQuery类、OrQuery类及相应的运算符
    // AndQuery类和OrQuery类以及它们的运算符都非常相似：

    // 15.9.4 eval函数
    // eval函数是我们这个查询系统的核心。每个eval函数作用于各自的运算对象，同时遵循的内在逻辑也有所区别：OrQuery的eval操作返回两个运算对象查询结果的并集，而AndQuery返回交集。
    // 与它们相比，NotQuery的eval函数更加复杂一些：它需要返回运算对象没有出现的文本行。
    // 为了支持上述eval函数的处理，我们需要使用QueryResult，在它当中定义了12.3.2节练习（第435页）添加的成员。
    // 我们的Query类使用了12.3.2节练习（第435页）为QueryResult定义的成员。

    // OrQuery::eval

    // AndQuery::eval

    // NotQuery::eval

    // 小结
    /**
     * 继承使得我们可以编写一些新的类，这些新类既能共享其基类的行为，又能根据需要覆盖或添加行为。动态绑定使得我们可以忽略类型之间的差异，其机理是在运行时根据对象的动态类型来选择运行函数的哪个版本。
     *   继承和动态绑定的结合使得我们能够编写具有特定类型行为但又独立于类型的程序。
     * 在C++语言中，动态绑定只作用于虚函数，并且需要通过指针或引用调用。
     * 当执行派生类的构造、拷贝、移动和赋值操作时，首先构造、拷贝、移动和赋值其中的基类部分，然后才轮到派生类部分。析构函数的执行顺序则正好相反，首先销毁派生类，接下来执行基类子对象的析构函数。
     *   基类通常都应该定义一个虚析构函数，即使基类根本不需要析构函数也最好这么做。将基类的析构函数定义成虚函数的原因是为了确保当我们删除一个基类指针，而该指针实际指向一个派生类对象时，
     *   程序也能正确运行。
    */

    // 术语表
    /**
     * 抽象基类（abstract base class） 含有一个或多个纯虚函数的类，我们无法创建抽象基类的对象。
     * 可访问的（accessible） 能被派生类对象访问的基类成员。可访问性由派生类的派生列表中所用的访问说明符和基类中成员的访问级别共同决定。
     *   例如，通过公有继承而来的一个公有成员对于派生类的用户来说是可访问的；而私有继承而来的公有成员是不可访问的。
     * 类派生列表（class derivation list） 罗列了所有基类，每个基类包含一个可选的访问级别，它定义了派生类继承该基类的方式。如果没有提供访问说明符，则当派生类通过关键字struct定义时继承是公有的；
     *   而当派生类通过关键字class定义时继承是私有的。
     * 派生类向基类的类型转换（derived-to-base conversion） 派生类对象向基类引用或者派生类指针向基类指针的隐式类型转换。
     * 直接基类（direct base class） 派生类直接继承的基类，直接基类在派生类的派生列表中说明。直接基类本身也可以是一个派生类。
     * 动态绑定（dynamic binding） 直到运行时才确定到底执行函数的哪个版本。在C++语言中，动态绑定的意思是在运行时根据引用或指针所绑定对象的实际类型来选择执行虚函数的某一个版本。
     * 动态类型（dynamic type） 对象在运行时的类型。引用所引对象或者指针所指对象的动态类型可能与该引用或指针的静态类型不同。基类的指针或引用可以指向一个派生类对象。
     *   在这样的情况中，静态类型是基类的引用（或指针），而动态类型是派生类的引用（或指针）。
     * 面向对象编程（object-oriented programming） 利用数据抽象、继承以及动态绑定等技术编写程序的方法。
     * 覆盖（override） 派生类中定义的虚函数如果与基类中定义的同名虚函数有相同的形参列表，则派生类版本将覆盖基类的版本。
     * 多态性（polymorphism） 当用于面向对象编程的范畴时，多态性的含义是指程序能通过引用或指针的动态类型获取类型特定行为的能力。
     * 私有继承（private inheritance） 在私有继承中，基类的公有成员和受保护成员是派生类的私有成员。
     * 纯虚函数（pure virtual） 在类的内部声明虚函数时，在分号之前使用了=0。一个纯虚函数不需要（但是可以）被定义。含有纯虚函数的类是抽象基类。
     *   如果派生类没有对继承而来的纯虚函数定义自己的版本，则该派生类也是抽象的。
     * 重构（refactoring） 重新设计程序以便将一些相关的部分搜集到一个单独的抽象中，然后使用新的抽象替换原来的代码。
     *   通常情况下，重构类的方式是将数据成员和函数成员移动到继承体系的高级别节点当中，从而避免代码冗余。
     * 静态类型（static type） 对象被定义的类型或表达式产生的类型。静态类型在编译时是已知的。
    */


    return 0;
}